#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

using namespace std;

namespace lh
{
	//BM6 判断链表是否有环
	//https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=295&tqId=605&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int x) : val(x), next(NULL) {}
    };

    class Solution {
    public:
        bool hasCycle(ListNode* head) {
            //有环使用快慢指针，必定相遇
            ListNode* fast = head, * slow = head;
            //若没环,一定是快指针先走到链表尾，fast走两步，防止野指针必须判断next也不为空，否则对野指针->next解引用出错
            while (fast != nullptr && fast->next != nullptr)
            {
                fast = fast->next->next;
                slow = slow->next;
                if (fast == slow)
                {
                    return true;
                }
            }
            return false;
        }
    };

    void test1()
    {
        ListNode* node1 = new ListNode(3);
        ListNode* node2 = new ListNode(2);
        ListNode* node3 = new ListNode(0);
        ListNode* node4 = new ListNode(-4);

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node2;

        cout << Solution().hasCycle(node1) << endl;
        delete node1;
        delete node2;
        delete node3;
        delete node4;

    }

    //BM7 链表中环的入口结点
    //https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=295&tqId=23449&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead) {
            //快慢指针
            ListNode* fast = pHead, * slow = pHead;

            while (fast != nullptr && fast->next != nullptr)
            {
                fast = fast->next->next;
                slow = slow->next;
                if (fast == slow)
                {
                    break;
                }
            }
            //若无环，返回空
            if (fast == nullptr || fast->next == nullptr)
            {
                return nullptr;
            }

            //有环，当前fast和slow都在环中相遇
            //重置fast,表头到环入口和相遇点到环入口距离相同
            fast = pHead;
            while (fast != slow)
            {
                fast = fast->next;
                slow = slow->next;
            }
            return fast;

        }
    };
    void test2()
    {
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(2);
        ListNode* node3 = new ListNode(3);
        ListNode* node4 = new ListNode(4);
        ListNode* node5 = new ListNode(5);

        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
        node5->next = node3;

        cout << Solution2().EntryNodeOfLoop(node1)->val << endl;
        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
    }
};


int main()
{
    //lh::test1();
    lh::test2();
    return 0;
}